iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 25
1
自我挑戰組

透過JavaScript學習演算法與資料結構系列 第 25

廣度優先搜尋法(Breadth First Search)

  • 分享至 

  • xImage
  •  

簡而言之,就是遍歷樹的每一層節點,遍歷一層後再往下一層遍歷節點。

img

程式碼如下:

class Tree{
  constructor(value){
    this.value=value;
    this.children = [];
  }
}

const BFS=(node, cb, depth = 0)=> {
  let queue = [];
  let nextQueue = [];
  queue.push(node);
  while (queue.length) {
    let current = queue.shift();
    cb(current, depth);
    current.children.forEach(child => {
      nextQueue.push(child);
    })
    if(!queue.length) {
      queue = nextQueue;
    nextQueue = [];
    depth++;
    }
  }
}

const breadthFirstSearch=(node, cb)=> {
  let queue = [];
  queue.push(node);
  while (queue.length) {
    let current = queue.shift();
    cb(current);
    if (current.children.length) {
      current.children.forEach(child => {
        queue.push(child);
      })
    }
  }
}

const tree = new Tree();

tree.value=1;
tree.children.push(new Tree(2));
tree.children.push(new Tree(3));
tree.children.push(new Tree(4));
tree.children[0].children.push(new Tree(5));
tree.children[1].children.push(new Tree(6));
tree.children[1].children.push(new Tree(7));
tree.children[2].children.push(new Tree(8));
tree.children[0].children[0].children.push(new Tree(9));
tree.children[1].children[0].children.push(new Tree(10));

breadthFirstSearch(tree, (node) => {
  console.log(node.value);
});

BFS(tree, (node, depth) => {
  console.log('value is ', node.value, ' at depth ', depth)
});

程式碼


上一篇
深度優先搜尋法(Depth Frist Search)
下一篇
ES6 Set介紹
系列文
透過JavaScript學習演算法與資料結構30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言